package dp.最优解;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 买卖股票的最佳时机121.java
 * @createTime 2024年03月07日 15:28:00
 */
public class 买卖股票的最佳时机121 {
	/*
    选择：选择在某条买入/卖出股票
    状态：天数，最大允许交易次数，股票的状态
    定义dp[i][k][0 or 1]其中
    i表示第i天，k表示第i天的时候的最大交易次数，0表示卖出1表示持有，
    所以求得是dp[i][k][0]的最大值

    状态转移
    dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+price[i])
               =max(昨天卖出了进口空仓，昨天卖进了今天卖出)
    basecase：
    dp[-1][...][0] = 0
    解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。

    dp[-1][...][1] = -infinity
    解释：还没开始的时候，是不可能持有股票的。
    因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

    dp[...][0][0] = 0
    解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。

    dp[...][0][1] = -infinity
    解释：不允许交易的情况下，是不可能持有股票的。
    因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

    dp[-1][...][0] = dp[...][0][0] = 0
    dp[-1][...][1] = dp[...][0][1] = -infinity

    状态转移方程：
    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

     */
	public int maxProfit(int[] prices) {
		int length = prices.length;
		int[][] dp = new int[length][2];
		for (int i = 0; i < prices.length; i++) {
			if (i == 0) {
				dp[i][1] = -prices[i];
				dp[i][0] = 0;
				continue;
			}
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
		}
		return dp[length - 1][0];
	}
}
